2019 Kakao Winter Internship

Tuple (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/64065
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool chk_ind(vector<vector<int>> dict, vector<vector<int>> s_trans){
for(int i=0; i<s_trans.size(); ++i){
sort(s_trans[i].begin(), s_trans[i].end());
sort(dict[i].begin(), dict[i].end());
}
for(int i=0; i<dict.size(); ++i){
if(find(s_trans.begin(), s_trans.end(), dict[i])==s_trans.end()) return false;
}
return true;
}
vector<int> solution(string s){
vector<int> answer, tmp;
vector<vector<int>> s_trans;
for(int i=0; i<s.length();){
if(s[i]=='{') {tmp.clear(); ++i; continue;}
if(s[i]=='}') {
if(s[i+1]!='}'){s_trans.push_back(tmp);}
++i;
continue;
}
if(s[i]==',') {++i; continue;}
if(s[i]>='0' && s[i]<='9'){
string num(1, s[i]);
while(s[++i]>='0' && s[i]<='9') num+=s[i];
if(find(answer.begin(), answer.end(), stoi(num))==answer.end()){
answer.push_back(stoi(num));
}
tmp.push_back(stoi(num));
}
}
sort(answer.begin(), answer.end());
do{
vector<vector<int>> dict;
for(int i=1; i<answer.size()+1; ++i){
vector<int> sub;
for(int j=0; j<i; ++j) sub.push_back(answer[j]);
dict.push_back(sub);
}
if(chk_ind(dict, s_trans)) return answer;
}while(next_permutation(answer.begin(), answer.end()));
answer.clear();
return answer;
}
void print_vec(vector<int> result){
if(!result.size()){
cout<<"NO VEC"<<endl;
return;
}
cout<<"[";
for(int i=0; i<result.size()-1; ++i) cout<<result[i]<<", ";
cout<<result[result.size()-1]<<"]"<<endl;
}
int main(void){
string s1="{{2},{2,1},{2,1,3},{2,1,3,4}}";
string s2="{{1,2,3},{2,1},{1,2,4,3},{2}}";
string s3="{{20,111},{111}}";
string s4="{{123}}";
string s5="{{4,2,3},{3},{2,3,4,1},{2,3}}";
print_vec(solution(s1));
print_vec(solution(s2));
print_vec(solution(s3));
print_vec(solution(s4));
print_vec(solution(s5));
return 0;
}
Crane Doll Draw (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/64061
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool chk_stack(vector<int>& stack){
int st_size=stack.size();
if(st_size<2) return false;
if(stack[st_size-1]==stack[st_size-2]){
stack.pop_back(); stack.pop_back();
return true;
}
return false;
}
int solution(vector<vector<int>> board, vector<int> moves){
int answer=0;
vector<int> stack;
for(int m: moves){
for(int i=0; i<board.size(); ++i){
if(board[i][m-1]){
stack.push_back(board[i][m-1]);
answer+=chk_stack(stack);
board[i][m-1]=0;
break;
}
}
}
answer*=2;
return answer;
}
int main(void){
vector<vector<int>> board={
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 3},
{0, 2, 5, 0, 1},
{4, 2, 4, 4, 2},
{3, 5, 1, 3, 1}
};
vector<int> moves={1, 5, 3, 5, 1, 2, 1, 4};
int result=solution(board, moves);
cout<<"result: "<<result<<endl;
return 0;
}
Rogue user (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/64064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;
bool is_ano(string real, string fake){
if(real.length()!=fake.length()) return false;
for(int i=0; i<real.length(); ++i){
if(fake[i]=='*') continue;
if(real[i]!=fake[i]) return false;
}
return true;
}
int chk(vector<string> banned_id, vector<string> ban){
assert(banned_id.size()==ban.size());
sort(ban.begin(), ban.end());
int sum;
do{
sum=0;
for(int i=0; i<ban.size(); ++i){
if(is_ano(ban[i], banned_id[i])) sum++;
}
if(sum==banned_id.size()) return 1;
}while(next_permutation(ban.begin(), ban.end()));
return 0;
}
int solution(vector<string> user_id, vector<string> banned_id){
int answer=0;
vector<bool> index(user_id.size(), 0);
for(int i=user_id.size()-banned_id.size(); i<user_id.size(); ++i){
index[i]=1;
}
do{
vector<string> ban;
for(int i=0; i<index.size(); ++i){
if(index[i]) ban.push_back(user_id[i]);
}
answer+=chk(banned_id, ban);
}while(next_permutation(index.begin(), index.end()));
return answer;
}
int main(void){
vector<string> user_id1={"frodo", "fradi", "crodo", "abc123", "frodoc"};
vector<string> user_id2={"frodo", "fradi", "crodo", "abc123", "frodoc"};
vector<string> user_id3={"frodo", "fradi", "crodo", "abc123", "frodoc"};
vector<string> banned_id1={"fr*d*", "abc1**"};
vector<string> banned_id2={"*rodo", "*rodo", "******"};
vector<string> banned_id3={"fr*d*", "*rodo", "******", "******"};
int result1=solution(user_id1, banned_id1);
int result2=solution(user_id2, banned_id2);
int result3=solution(user_id3, banned_id3);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
cout<<"reulst3: "<<result3<<endl;
return 0;
}
Crossing the Stepping stone (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/64062
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool cross(vector<int>& stones, const int k){
int avail=k;
for(int i=0; i<stones.size(); ++i){
if(!avail) return 0;
if(stones[i]!=0){
stones[i]--;
avail=k;
}else{
avail--;
}
}
return 1;
}
int solution(vector<int> stones, int k){
int answer=0;
while(cross(stones, k)) answer++;
return answer;
}
int main(void){
vector<int> stones={2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
int k=3, result;
result=solution(stones, k);
cout<<"result: "<<result<<endl;
return 0;
}
Assign Hotel rooms (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/64063
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> solution(ll k, vector<ll> room_number){
vector<ll> answer;
vector<bool> room(k, 0);
ll tmp;
for(ll cus: room_number){
tmp=cus-1;
while(room[tmp]) {tmp++;}
room[tmp]=1;
answer.push_back(tmp+1);
}
return answer;
}
int main(void){
ll k=10;
vector<ll> room_number={1, 3, 4, 1, 3, 1};
vector<ll> result=solution(k, room_number);
cout<<"[";
for(int i=0; i<result.size()-1; ++i) cout<<result[i]<<", ";
cout<<result[result.size()-1]<<"]"<<endl;
return 0;
}